package reviewAlgorithms.search;

import java.util.ArrayList;
import java.util.List;

public class NumSquares {
    public static void main(String[] args) {
        System.out.println(numSquares(184));
    }
    public static int numSquares(int n) {
        if (n < 1){
            return 0;
        }
        int num = (int) Math.sqrt(n);
        int level = 0;
        int sum = 0;
        List<Integer> oneRes = new ArrayList<>();
        List<Integer> res = new ArrayList<>();

        getNumSquares(sum,level,num,oneRes,res,n);
        System.out.println(res.toString());
        return res.size();
    }

    private static void getNumSquares(int sum, int level, int num, List<Integer> oneRes, List<Integer> res, int target) {
        if (sum >= target){
            if (sum == target ){
                if (res.size() == 0){
                    res.addAll(oneRes);
                }else if (level < res.size()){
                    res.clear();
                    res.addAll(oneRes);
                }
            }
            return;
        }
        if (!res.isEmpty() && level > res.size()){
            return;
        }
        for (int i = num; i >= 1 ; i--) {
            sum += i * i;
            oneRes.add(i * i);
            getNumSquares(sum,level + 1,num,oneRes,res,target);
            sum -= i * i;
            oneRes.remove(oneRes.size() - 1);
        }
    }
}
